package leetCode.q32;

public class Me {
    /**
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     */
    public int longestValidParentheses(String s) {
        int res = 0;
        char[] arr = s.toCharArray();
        int len = s.length();
        if(len <= 1) return 0;

        int[] dp = new int[len];

        if(arr[0] == '('&&arr[1] == ')') dp[1] = 2;
        res = Math.max(res,dp[1]);

        for(int i = 2;i<len;i++){
            // compute the dp[i]

            if(arr[i] == ')'){
                if(arr[i-1] == '(') dp[i] = 2+dp[i-2];
                if(arr[i-1] == ')') {
                    int lenx = dp[i-1];
                    // i - tou = lenx tou = i-lenx
                    int head = i-lenx;
                    if(head-1>=0 && arr[head-1] == '(') {
                        dp[i] = 2+dp[i-1];
                    }
                    if(head-2>=0){
                        dp[i]+=dp[head-2];
                    }
                }
            }
            res = Math.max(res,dp[i]);
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Me().longestValidParentheses("(()())"));
    }
}
